package com.chj.dfs.class04;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Code09_CombinationSumII {
	public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
		List<List<Integer>> list = new LinkedList<>();
		Arrays.sort(candidates);// 先排序
		backtrack(list, new ArrayList<>(), candidates, target, 0);
		return list;
	}

	private static void backtrack(List<List<Integer>> list, List<Integer> cur, int[] candidates, int target,
			int start) {
		if (target == 0) {
			list.add(new ArrayList<>(cur));
			return;
		}
		for (int i = start; i < candidates.length; i++) {
			if (target < candidates[i])
				continue;
			if (i > start && candidates[i] == candidates[i - 1])
				continue; // 去掉重复的
			cur.add(candidates[i]);
			backtrack(list, cur, candidates, target - candidates[i], i + 1);
			cur.remove(cur.size() - 1);
		}
	}

	public static void main(String[] args) {
		{
			int[] nums = { 10, 1, 2, 7, 6, 1, 5 };
			int target = 8;
			List<List<Integer>> lists = combinationSum2(nums, target);
			System.out.println(lists);
		}

//		[
//		  [1, 7],
//		  [1, 2, 5],
//		  [2, 6],
//		  [1, 1, 6]
//		]
	}
}
